package org.example.sward.tooffer;

import org.example.ch04.tree.TreeNode;

public class Offer68 {
    public static void main(String[] args) {
        Offer68 offer68 = new Offer68();

        TreeNode root = new TreeNode();
        root.val = 3;

        TreeNode node5 = new TreeNode(5);
        TreeNode node3 = new TreeNode(3);

        TreeNode node1 = new TreeNode(1);

        TreeNode node6 = new TreeNode(6);
        TreeNode node2 = new TreeNode(2);



        TreeNode node0 = new TreeNode(0);
        TreeNode node8 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node4 = new TreeNode(4);

        root.left = node5;
        root.right = node1;

        node5.left = node6;
        node5.right = node2;

        node2.left = node7;
        node2.right = node4;
        node1.left = node0;
        node1.right = node8;


        TreeNode nodeP = new TreeNode(7);
        TreeNode nodeQ = new TreeNode(0);

        TreeNode result =  offer68.lowestCommonAncestor(root,nodeP,nodeQ);
        System.out.println(result.val);

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root.val == p.val || root.val == q.val) {
            return root;
        }
        System.out.println("当前root的值:"+root.val);
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        return root;
    }



}
